#include "./advance-sort.h"

void shellSort(SqList &list)
{
	// 增量，最后必须是1，希尔排序是把相隔一定增量的元素进行跳跃式地插入排序，并每一轮后缩小增量达到完成排序的目的
	// 可以理解为分组的标识，假设表长为9，按照下面代码增量为4，则第一次先对表中第0,4,8个元素进行插入排序，也就是说第一趟把表中相隔4个元素的元素拿出来插入排序，进而再对第1,5个元素进行排序...
	// 第一轮完成后，增量缩减为2，那么再把表中第0,2,4,6,8元素拿出来插入排序，这一趟完成后再进而对1,3,5,7元素进行排序...
	// 增量一直这么缩减，先使得表中数据先大体有序，然后使得最后进行完整的插入排序时交换次数最少
	int increment = list.length;
	int tmp, j;
	do
	{
		// 增量每次缩减，最后一次增量会变成1
		increment = increment / 3 + 1;
		// 对相隔一定增量的元素进行插入排序
		for (int i = increment; i < list.length; i++)
		{
			// 比较相隔一定增量的元素大小，若后面的小于前面的，则进行插入排序
			if (list.elem[i] < list.elem[i - increment])
			{
				// 把第i个元素拿出来，并把它插入到前面合适的位置
				tmp = list.elem[i];
				for (j = i - increment; j >= 0 && tmp < list.elem[j]; j -= increment)
				{
					list.elem[j + increment] = list.elem[j];
				}
				list.elem[j + increment] = tmp;
			}
		}
	} while (increment > 1);
}

/**
 * 堆排序-调整为大根堆，由于在二叉树（堆）中，结点索引从1开始编号，但是列表中是从0开始编号，所以在进行对列表元素操作时，下标会减1
 * @param list 传入存放二叉树结点的列表
 * @param start 开始结点的索引（双亲结点），为二叉树结点编号（从1开始的）
 * @param end 结束结点的索引（子节点），为二叉树结点编号（从1开始的）
 */
void heapAdjust(SqList &list, int start, int end)
{
	// 从双亲结点的左孩子（索引为j = 2 * start）开始进行比较
	for (int j = 2 * start; j <= end; j *= 2)
	{
		// 如果说右孩子（j + 1）比左孩子（j）的值要大，则把j指向更大的右孩子以在后续比较交换
		if (j < end && list.elem[j - 1] < list.elem[j])
		{
			j++;
		}
		// 双亲结点比子节点小的话，则进行交换操作
		if (list.elem[start - 1] < list.elem[j - 1])
		{
			swap(list, start - 1, j - 1);
			// 然后以这个子节点开始继续向下比较调整
			start = j;
		}
	}
}

void heapSort(SqList &list)
{
	/* 堆排序就是先把列表构造成大根堆，然后逐一取出根，并把剩余元素继续构造成大根堆，如此往复，就可以得到一个有序列表
	 * 大根堆是每个结点的值都大于等于其左右孩子结点的值的二叉树
	 * 二叉树的性质：按照层次遍历给二叉树表述索引，假设索引i=1的结点为根，那么对于i>1的结点，其双亲结点索引为└i / 2┘，反过来下标为i的结点，其孩子结点分别为2i和2i + 1
	 */
	// 第一步：将原始无序列表构造成大根堆，从最后一个双亲结点开始进行调整
	// 由于在二叉树（堆）中，结点索引从1开始编号，但是列表中是从0开始编号，所以在进行调整操作时，传入的是二叉树索引编号
	for (int i = list.length / 2; i > 0; i--)
	{
		heapAdjust(list, i, list.length);
	}
	// 第二步：把每一个最大的结点放到最后面去，然后对剩下第0到length - i的结点进行重新构造成大根堆
	for (int i = list.length - 1; i > 0; i--)
	{
		// 把最大的结点即根放到后面去，然后对前面剩下结点重新构造
		swap(list, 0, i);
		// 这里i是列表索引，因此进行堆调整时，要传入二叉树结点编号，加1即可
		// 对列表中前面第0到i - 1的结点重新进行构造成大根堆
		heapAdjust(list, 1, i);
	}
}

/**
 * 融合列表为整体有序的，传入的list中，第start到mid这一部分是有序的，第mid + 1到end这一部分是有序的
 * 该函数用于将两部分有序的列表融合为有序的一部分使得第start到end都是有序的
 * @param list 待融合的列表
 * @param start 列表有序的第一部分的起始索引
 * @param mid 列表有序的第一部分的终止索引
 * @param end 列表有序的第二部分的终止索引
 */
void merge(SqList &list, int start, int mid, int end)
{
	// 创建两个辅助数组，把list第start到mid和第mid + 1到end这两部分复制进去
	int leftLength = mid - start + 1; // 左辅助数组长度
	int rightLength = end - mid;	  // 右辅助数组长度
	int leftSortedPart[leftLength], rightSortedPart[rightLength];
	for (int i = start; i <= mid; i++)
	{
		leftSortedPart[i - start] = list.elem[i];
	}
	for (int i = mid + 1; i <= end; i++)
	{
		rightSortedPart[i - mid - 1] = list.elem[i];
	}
	// 然后把这两个数组中元素由小到大地并入回原列表第start到end的空间中去
	int leftIndex = 0, rightIndex = 0; // 两个辅助数组的下标指针
	for (int i = start; i <= end; i++)
	{
		// 当左辅助数组当前元素比右辅助数组的小，则插入进原列表完成归并
		// 如果说当前左辅助数组都被插入完了，那就说明小的都归并完了，直接到else归并右辅助数组的元素
		// 反过来如果说当前右辅助数组都被插入完了，那么只需归并左辅助数组元素即可
		if (rightIndex >= rightLength || (leftIndex < leftLength && leftSortedPart[leftIndex] < rightSortedPart[rightIndex]))
		{
			list.elem[i] = leftSortedPart[leftIndex];
			leftIndex++;
		}
		else
		{
			list.elem[i] = rightSortedPart[rightIndex];
			rightIndex++;
		}
	}
}

/**
 * 归并排序的递归部分，对list的第start到end元素进行归并排序
 * @param list 列表
 * @param start 排序起始索引
 * @param end 排序终止索引
 */
void mergeSortRecursive(SqList &list, int start, int end)
{
	// 当列表被分为只有一个元素的时候，则停止递归
	if (start >= end)
	{
		return;
	}
	// 将传入的列表根据指定范围一分为二
	int mid = (start + end) / 2;
	// 递归进行二路归并排序
	mergeSortRecursive(list, start, mid);
	mergeSortRecursive(list, mid + 1, end);
	// 开始进行归并融合
	merge(list, start, mid, end);
}

void mergeSortR(SqList &list)
{
	mergeSortRecursive(list, 0, list.length - 1);
}

/**
 * 把list分为若干个长度为subLength的子序列，然后对它们两两进行归并
 * @param list 传入列表
 * @param subLength 每个子序列的长度
 */
void mergePass(SqList &list, int subLength)
{
	int count = list.length / subLength;  // 子序列的个数
	int groupCount = count / 2;			  // 每两个子序列为一组进行归并，表示前面可以一趟完成归并的组数
	int remain = list.length % subLength; // 还剩下最后几个无法被平均分的个数，将组成最后一个子序列
	// 开始两两归并
	for (int i = 0; i < groupCount; i++)
	{
		merge(list, i * 2 * subLength, (i * 2 + 1) * subLength - 1, (i + 1) * 2 * subLength - 1);
	}
	// 对剩下还没有归并的组进行处理
	if (count % 2 == 1 && remain != 0)
	{
		merge(list, groupCount * 2 * subLength, (groupCount * 2 + 1) * subLength - 1, list.length - 1);
	}
}

void mergeSort(SqList &list)
{
	// 子序列长度，先开始为1
	int subLength = 1;
	while (subLength < list.length)
	{
		// 把list拆成若干个长度为subLength的子序列并两两进行归并为有序列表
		mergePass(list, subLength);
		// 每次进行两两归并后，子序列长度变为原来两倍再进行两两归并
		subLength *= 2;
	}
}

/**
 * 在列表的low到high范围中选取一个枢轴变量，并把列表中比其小的移到枢轴变量前面，大的移到其后面，最后返回枢轴变量所在的索引
 * 该函数使用三数取中法
 * @param list 列表
 * @param low 起始索引
 * @param high 终止索引
 * @return 最后枢轴变量位置
 */
int partition(SqList &list, int low, int high)
{
	int mid = (low + high) / 2;
	// 先保证两边左边最小
	if (list.elem[low] > list.elem[high])
	{
		swap(list, low, high);
	}
	// 然后保证中间比右边小
	if (list.elem[mid] > list.elem[high])
	{
		swap(list, high, mid);
	}
	// 最后把中等值换到左边
	if (list.elem[mid] > list.elem[low])
	{
		swap(list, mid, low);
	}
	// 此时，low为三数的中间值，将其作为枢轴
	int pivot = list.elem[low];
	while (low < high)
	{
		// 先开始，枢轴变量下标是low
		// 从后往前找到第一个小于枢轴的进行交换
		while (low < high && list.elem[high] >= pivot)
		{
			high--;
		}
		if (low < high)
		{
			swap(list, low, high);
			low++;
		}
		// 交换之后，枢轴变量下标为high
		// 这时从前往后找到第一个大于枢轴的进行交换
		while (low < high && list.elem[low] <= pivot)
		{
			low++;
		}
		if (low < high)
		{
			swap(list, low, high);
			high--;
		}
		// 交换后，枢轴的下标又变回了low
	}
	return low;
}

/**
 * 快速排序的递归部分，对列表中索引为low到high这一部分元素进行快速排序
 * @param list 待排序列表
 * @param low 起始索引
 * @param high 终止索引
 */
void quickSortRecursive(SqList &list, int low, int high)
{
	int pivotIndex; // 枢轴变量的索引
	if (low < high)
	{
		pivotIndex = partition(list, low, high);
		quickSortRecursive(list, low, pivotIndex - 1);	// 对枢轴之前的部分进行递归排序
		quickSortRecursive(list, pivotIndex + 1, high); // 对枢轴之后的部分进行递归排序
	}
}

void quickSort(SqList &list)
{
	quickSortRecursive(list, 0, list.length - 1);
}